package problems.contest;

import java.util.Arrays;

/**
 * 第349场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-349/</p>
 *
 * @author dubulingbo, 2023/6/13 19:44.
 */
public class WCT349 {
    /**
     * T1|2733. 既不是最小值也不是最大值
     * <p>https://leetcode.cn/problems/neither-minimum-nor-maximum/</p>
     */
    public int findNonMinOrMax(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        Arrays.sort(nums, 0, 3);
        return nums[1];
    }

    public int findNonMinOrMax1(int[] nums) {
        int min = 101;
        int max = 0;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        for (int num : nums) {
            if (num != min && num != max) {
                return num;
            }
        }

        return -1;
    }


    /**
     * T2|2734. 执行子串操作后的字典序最小字符串
     * <p>https://leetcode.cn/problems/lexicographically-smallest-string-after-substring-operation/</p>
     */
    public String smallestString(String s) {
        /**
         * 1. 找到第一个可以替换的位置，即 chs[i] > 'a'
         * 2. 从当前位置找到连续的一段可替换的位置
         */
        int n = s.length();
        int replaceIndex = -1;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) > 'a') {
                replaceIndex = i;
                break;
            }
        }
        // 没有替换位置，即全部为 'a'，替换最后的 'a' 即可
        if (replaceIndex == -1) return s.substring(0, n - 1) + "z";

        // 改成可变字符串
        StringBuilder ret = new StringBuilder(s);
        while (replaceIndex < n && s.charAt(replaceIndex) > 'a')
            ret.setCharAt(replaceIndex, (char) (s.charAt(replaceIndex++) - 1));

        return ret.toString();
    }


    /**
     * T3|2735. 收集巧克力
     * <p>https://leetcode.cn/problems/collecting-chocolates/</p>
     */
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        long[] sum = new long[n];

        // 操作 i 次后，所需的转换成本
        for (int i = 0; i < n; i++) sum[i] = (long) i * x;

        // 子数组左端点
        for (int i = 0; i < n; i++) {
            int min = nums[i];
            // 子数组右端点（把数组视作环形的）
            for (int j = i; j < n + i; j++) {
                // 从 nums[i] 到 nums[j % n] 的最小值
                min = Math.min(min, nums[j % n]);
                // 累加操作 j-i 次的成本
                sum[j - i] += min;
            }
        }

        long ans = Long.MAX_VALUE;
        for (long s : sum) ans = Math.min(ans, s);

        return ans;
    }
}
